#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <tr1/unordered_map>
#include <vector>
#include <boost/functional/hash.hpp>
#include <math.h>
#include <string.h>
#include <sstream>
#include <boost/format.hpp>
#include <fstream>
#include <boost/algorithm/string.hpp>
#include <boost/lexical_cast.hpp>

using namespace std;
using namespace tr1;
using namespace boost;

typedef vector<int> ITEM_KEY;

size_t hash_value(ITEM_KEY const &key) {
	size_t seed = 0;
	boost::hash_combine(seed, key[0]);
	boost::hash_combine(seed, key[1]);
	return seed;
}

size_t hash_value(int i, int j) {
	size_t seed = 0;
	boost::hash_combine(seed, i);
	boost::hash_combine(seed, j);
	return seed;
}

struct Bucket;

struct Item {
	ITEM_KEY key;
	float weight, delta;
	Bucket * parent;
	size_t hashvalue;

	Item();
	Item(ITEM_KEY _key, float _weight, float _delta) {
		key = _key;
		weight = _weight;
		delta = _delta;
		parent = NULL;
		hashvalue = hash_value(key);
	}

	bool operator<(const Item& rhs) {
		return weight < rhs.weight;
	}

	bool operator==(const Item& rhs) {
		return hash_value(key) == hash_value(rhs.key);
	}

	/*size_t hashvalue() const {
		size_t seed = 0;
		boost::hash_combine(seed, key[0]);
		boost::hash_combine(seed, key[1]);
		return seed;
	}*/

	const string toString() {
		ostringstream oss;
		oss << "[(" <<  key[0] << "," << key[1]<< ")," << weight << ","<< delta  << "] ";
		return oss.str();
	}
};

size_t hash_value(Item const& i) {
	size_t seed = 0;
	boost::hash_combine(seed, i.key[0]);
	boost::hash_combine(seed, i.key[1]);
	return seed;
}

typedef unordered_map<int, Item> ITEM_MAP;
typedef set<Item*> ITEM_SET;

struct Bucket {
	int key;
	Bucket * prev,* next;
	ITEM_SET elements;


	Bucket(int _key, Bucket *_prev, Bucket *_next ) {
		key = _key;
		prev = _prev;
		next = _next;
	}

	void add(Item *i) {
		elements.insert(i);
	}

	void remove(Item *i ) {
		ITEM_SET::iterator it = elements.find(i);
		elements.erase(*it);
	}

	bool has_elements() {
		return elements.size() > 0;
	}


	bool operator<(const Bucket& rhs) {
			return key < rhs.key;
	}

	bool operator==(const Bucket& rhs) {
		return key == rhs.key;
	}

	size_t hashvalue() const {
	    boost::hash<int> hasher;
	    return hasher(key);
	}

	const string toString() {
		ostringstream oss;
		ITEM_SET::iterator it = elements.begin();
		int _prev = prev != NULL ? (*prev).key : -1;
		int _next = next != NULL ? (*next).key : -1;
		oss << "bucket " << key << ": " << _prev << ":" << _next <<  ":";
		for (; it != elements.end(); it++) {
			oss << (*(*it)).toString() << (*(*it)->parent).key;
		}
		return oss.str();
	}
};

size_t hash_value(Bucket const&b) {
    boost::hash<int> hasher;
    return hasher(b.key);
}

typedef unordered_map<int, Bucket> BUCKET_MAP;


class StreamSummary {

private :
	ITEM_MAP items;
	BUCKET_MAP buckets;
	void add_item(int i, int j, float w);
	void increase(int i, int j, float w);
	Item get_min_el() ;
	void replace_min(int i, int j, float w);
	int min_bucket;

public:
	unsigned int k;
	StreamSummary(int k);
	void insert(int i, int j, float w) ;
	const string toString();
};
